A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。今天小编就为大家演示一遍A*算法的运算过程并用A*求解SCIO2005骑士精神的例题。

谈到广度优先搜索就不得不说深度优先搜索，他们是一对孪生兄弟。深度优先搜索（DFS）的搜索方式是，不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路。而广度优先搜索（BFS）的搜索方式是，面临一个路口时，把所有的岔路口都记下来，先选择其中一个进入，然后将它的分路情况记录下来，最后再返回来进入另外一个岔路，并重复这样的操作。

例如如图所示的案例，从黑色起点出发，目标为红色方块（假设不能斜着走）。第一次搜索只有两个方块可以选择，选择这两个方块并标记为走一步可以到达的地方。记录所有的岔路口，然后选择其中一个方向走进去。例如走黑点方块上面的那一个，然后将这个路口可走的方向记录下来并标记为2，意思是走两步可以到达的地方。很显然有三个方块是走两步就可以到达的地方。依此类推，分别继续标记3、4直到标记到红色方块。

「A *（A-star）」算法是静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。小编将用先图示演示一遍A*算法的运行过程，再介绍一段A*算法的代码，帮助小伙伴们更好地理解和运用A*。

如下图所示，需要找到从绿色方块出发，到红色方块的最短路径。蓝色区域为不可通行区域，需要绕道。

「第一步：开始搜索」

将起点周围的7个点纳入一个待检查列表A（起点正下方的点不能经过，因此忽略），这里的思想与前文介绍的BFS算法的思路类似。需要注意的是必须标注这些进入列表A的节点的父节点，以便在接下来的步骤中形成最短路径。结果如下图所示。

「第二步：计算成本」

假设总成本为f(n)，每个方格的f(n)都由当前成本g(n)和启发式信息计算函数h(n)组成，即f(n)=g(n)+h(n)。

当前成本g(n)就是指从起点到当前方格的路径长度，例如在本例中横向和纵向的移动代价为10，对角线的移动代价为14（√2）。那么在列表A中的最小g(n)就是10。

启发式信息计算函数h(n)指从当前方格到终点的估算成本（永远不会高估距离），这里我们可以使用曼哈顿距离来估算。所谓曼哈顿距离，其实就是获得两个方格之间的行数差，并将其与列数差相加而得到。例如下图中1号方格与0号方格和，曼哈顿距离为行差加列差：h(n)=4+6=10。

「第三步：继续搜索」

有第二步我们算出来每个方格的成本，显而易见，起点正右方的方格成本最低。

选择该方格，将它放入列表B（已检查列表）。接着检视其相邻方格，若相邻方格可走且不在列表A中，则将他们加入；若相邻方格已经在列表A中，则检查这条路径是否更优，也就是说经由当前方格是否具有更小的g(n)。若有更小的g(n)，则将那个方格的父亲设为当前选中的方格，然后重新计算成本。

在本例中，把首先选择的成本为40的方格从列表A中移出，移到已检查列表B中。它的右侧三块都是不能走的，左边是在列表B中的起点，没有新加入列表的方格。现在比较它相邻方格是否经过它成本更低，没有发现经由当前方格的更好路径，因此我们不做任何改变。

那么是时候选择下一个待处理方格了。按照成本计算，有两个方格的成本都是54，两者都可以作为下一个目标，简便起见我们就选择下面一个方格。如第一步，将新方块四周未进入列表A的方块加入列表A，如下图。

再次计算所有列表A中方块的成本：

选择成本为54的方格作为新的当前方格，将它四周的空余方格加入列表A。

当前方块没有其他可操作的内容了，我们进入下一方块。此时的成本最小方块为起点上面和起点左边的方块，都是60, 我们选择上面的方块。先将左上角的方块放入列表A。注意，此时检查当前方块正上方的方块时可以发现，经由当前方块其成本更低，因此改变其“父亲”。

接下来的步骤与之前类似：

如图，我们的最短路径长度就是56。那么我们怎么样去确定实际路径呢？很简单，从终点开始，按着箭头向父节点移动，这样你就被带回到了起点，这就是你的路径。

「A*算法总结：」

「1、」把起点加入待检查列表A中。

「2、」重复如下过程：

「a.」 遍历列表A，查找成本f(n)最小的节点，把它作为当前要处理的节点。

「b.」 把这个节点移到已检查的列表B中。

「c.」 对当前方格的 8 个相邻方格的每一个方格

◆ 如果它是不可抵达的或者它在列表B中，忽略它。

◆ 如果它不在列表A中，则将它加入A，并且把当前方格设置为它的父亲，记录该方格的成本f(n)。

◆ 如果它已经在列表A中，检查这条路径是否更好，用g(n)作参考。更小的g(n)表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的g(n)和f(n)。

「d.」 停止，当你

◆ 把终点加入到了列表A中，此时路径已经找到了

◆ 查找终点失败，并且列表A是空的，此时没有路径。3.保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

「下面是一道可以使用A*算法来做的题目：」

（题目来源：SCOI 2005 骑士精神）

一个5*5的棋盘上有12个黑骑士和12个白骑士，有且仅有一个空位。“骑士”棋子的移动方式基本等同于中国象棋中的马，即走“日”字。现在给定棋盘上棋子的一个状态，求使其恢复如图初始状态的棋盘最少需要多少步。

棋盘的目标状态

「输入格式」：第一行有一个正整数T(T